import java.sql.SQLOutput;
import java.util.Stack;

/**
 * 二叉搜索树
 * 二叉排序树
 */
public class MyBinarySearchTree {

    //创建节点类
    public static class TreeNode{
        int key;
        TreeNode left;
        TreeNode right;

        public TreeNode(int key){
            this.key = key;
        }
    }

    //根节点
    private TreeNode root;

    //添加节点
    public boolean put(int key){
        //1.判断此时的树是否为空树，如果是空树将元素添加到根节点
        if(root == null){
            root = new TreeNode(key);
            return true;
        }

        //2.不为空树需要先找到插入节点的位置,遍历搜索树
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            //根节点的值大于目标值,插入到左子树
            if(cur.key > key){
                parent = cur;
                cur = cur.left;
            }
            //根节点值小于目标值，插入到右子树
            else if(cur.key < key){
                parent = cur;
                cur = cur.right;
            }
            //根节点值与目标值相等，不能插入
            else return false;
        }

        //此时的cur位置就是需要插入的元素位置
        TreeNode node = new TreeNode(key);
        if(parent.key > key){
            parent.left = node;
        }else{
            parent.right = node;
        }
        return true;
    }

    //查找函数
    public boolean search(int key){
        //1.判断是否为空树
        if(root == null) return false;

        //2.遍历搜索树
        TreeNode cur = root;
        while(cur != null){
            //找到目标节点返回
            if(cur.key == key) return true;
            //当前节点值小于目标性，在右树搜索
            else if(cur.key < key) cur = cur.right;
            //当前节点值大于目标值，在左树搜索
            else cur = cur.left;
        }
        return false;
    }

    //中序遍历
    public void inorder(){
        if(root == null) return;

        //1.申请一个栈
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        System.out.print("[ ");
        while(!stack.empty() || cur != null){
            //将所有左节点添加到栈中
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //此时cur是最左边的节点
            //出栈，打印
            TreeNode tem = stack.pop();
            System.out.print(tem.key + " ");

            //判断右子树是否为空，不为空加入
            if(tem.right != null){
                cur = tem.right;
            }
        }
        System.out.println("]");
    }

    //删除节点：先查找需要删除的节点，如果找不到返回false
    //找到节点：1.节点的左子树不存在；2节点的右子树不存在；
    //3.左右子树都存在
    public boolean delete(int key){
        if(root == null) return false;

        //查找节点
        TreeNode parent = null,cur = root;
        while(cur != null) {
            if (cur.key == key) break;
            else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

            //判断是否没有找到目标值
            if(cur == null) return false;

            //找到目标值
            //1.目标节点没有左孩子子树
            if(cur.left == null && cur.right != null){
                if(root == cur) root = cur.right;
                else if(parent.left == cur) parent.left = cur.right;
                else parent.right = cur.right;
            }
            //2.目标节点没有右子树
            else if(cur.left != null && cur.right == null){
                if(root == cur) root = cur.left;
                else if(parent.left == cur) parent.left = cur.left;
                else parent.right = cur.left;
            }
            //3.左右子树都不为空
            else{
                //需要找到目标值右子树中最小的节点替换
                TreeNode pt = cur,target = cur.right;
                while(target.left != null){
                    pt = target;
                    target = target.left;
                }

                //替换目标值
                cur.key = target.key;

                //删除target节点
                if(cur.right == target){
                    cur.right = target.right;
                }else{
                    pt.left = target.right;
                }
            }
        return true;
    }

    public static void main(String[] args) {
        MyBinarySearchTree binarySearchTree = new MyBinarySearchTree();
       int[] arr = {4,2,6,1,3,5,7};
       for(int x : arr) binarySearchTree.put(x);

        System.out.print("中序遍历：");
       binarySearchTree.inorder();

       binarySearchTree.delete(2);
       binarySearchTree.delete(6);
        System.out.print("删除后的中序遍历：");
       binarySearchTree.inorder();

       //查找元素
        System.out.println("元素是否存在:" + binarySearchTree.search(2));
        System.out.println("元素是否存在:" + binarySearchTree.search(1));
    }

}
